package code.D1221;

/**
 * author： yeswater
 * create： 2023/12/22
 * <p>
 * 分割等和子集 01背包问题
 */
public class T416 {
    public boolean canPartition(int[] nums) {
        int n = nums.length;
        
        // 等和子集的和必然是总和的一半
        int sum = 0;
        for (int num : nums) {
            sum += num;
        }
        int target = sum / 2;
        
        // 对应了总和为奇数的情况，注定不能被分为两个等和子集
        if (target * 2 != sum) {
            return false;
        }
        
        int[][] f = new int[n][target + 1];
        // 先处理考虑第一件物品的情况
        for (int i = 1; i < n; i++) {
            int t = nums[i];
            for (int j = 0; j <= target; j++) {
                // 不选第一件商品
                int no = f[i-1][j];
                // 选第一件商品
                int yes = j >= t ? f[i-1][j-t] +  t : 0;
                f[i][j] = Math.max(yes, no);
            }
        }
        // 如果最大价值等于 target， 说明可以拆分成两个等和子集
        return f[n-1][target] == target;
    }
}
